package com.tgy.programmer_code_interview_guide._04_recursion_dynamicProgramming;

public class _01_斐波拉契数 {

    public static int fib(int n) {

//        int[] cache = new int[n+1];
//        cache[1] = 1;
//        cache[2] = 1;
//        return cacheDoFib(n,cache);

        if (n <= 2) {

            return 1;
        }

        int tmp;
        int first = 1, second = 1;
        System.out.print(first+"," + second);
        for (int i = 3; i <= n; i++) {

            tmp = second;
            second = first + second;
            first = tmp;

            System.out.print("," + second);
        }

        return second;
    }

    private static int doFib(int n) {

        if (n <= 2) {

            return 1;
        }

        return doFib(n - 1) + doFib(n - 2);
    }

    private static int cacheDoFib(int n, int[] cache) {

        if (cache[n] > 0) {

            return cache[n];
        }

        cache[n] = cacheDoFib(n-1,cache) + cacheDoFib(n-2,cache);
        return cache[n];
    }

    public static void main(String[] args) {

        /**
         * 1,1,2,3,5
         */
        fib(45);
    }

}
